package com.zlsy.learning.leetcode.sort;

import java.util.Arrays;

/**
 * @author zhouliang
 * @date 2020/8/25 16:50 归并排序演示
 */
public class MergeSortByMe {

  public static void main(String[] args) {
    int[] a = new int[] {1, 5, 6, 2, 3, 4};
    int n = a.length;
    mergeSort(a, n);
  }

  private static void mergeSort(int[] a, int n) {
    mergeSortInternally(a, 0, n - 1);
    System.out.println(Arrays.toString(a));
  }

  private static void mergeSortInternally(int[] a, int p, int r) {
    // 找到递归的退出条件
    if (p >= r) {
      return;
    }
    // 找到分而治之分段的中间点（我们知道对于int的类型/2，取得是前中位。比如5/2=2。a[2]）
    int q = p + (r - p) / 2;
    // 第一段递归直到退出
    mergeSortInternally(a, p, q);
    // 第二段递归直到退出
    mergeSortInternally(a, q + 1, r);
    // 排序合并（从从小段到最大的端）
    //    merge(a, p, q, r);

    mergeBySentry(a, p, q, r);
  }

  private static void merge(int[] a, int p, int q, int r) {
    int i = p;
    int j = q + 1;
    // 取一个k=0作为临时数组的index
    int k = 0;
    // 临时数组应该多大？取决于存放多少数据：即分段的长度(每段分过之后我们就得看成完整段)，即 r-p+1，而不是r-p+1除以2
    int[] temp = new int[r - p + 1];
    // 排序： i代表的是整段里面第一段的开始节点，j代表的是第二段里面的开始节点
    while (i <= q && j <= r) {
      // 排序
      if (a[i] <= a[j]) {
        temp[k++] = a[i++];
      } else {
        temp[k++] = a[j++];
      }
    }
    // 整段里面比较之后子数组还未处理完的数据，要找打未处理完的index，放到temp里面
    int start = i;
    int end = q;
    if (j <= r) {
      start = j;
      end = r;
    }

    // 将未处理完的数据放入temp
    while (start <= end) {
      temp[k++] = a[start++];
    }

    // 然后将temp排好序合并好的数组 拷贝a处理该数组的位置
    for (int l = 0; l < temp.length; l++) {
      // a的位置 即p开始的位置
      a[p + l] = temp[l];
    }
  }

  private static void mergeBySentry(int[] arr, int p, int q, int r) {
    int[] leftArr = new int[q - p + 2];
    int[] rightArr = new int[r - q + 1];

    // 初始化左边的数组
    for (int i = 0; i < leftArr.length; i++) {
      leftArr[i] = arr[p + i];
    }
    leftArr[q - p + 1] = Integer.MAX_VALUE;

    // 初始化右边的数组
    for (int j = 0; j < rightArr.length - 1; j++) {
      rightArr[j] = arr[j + q + 1];
    }
    rightArr[r - q] = Integer.MAX_VALUE;

    int i = 0;
    int j = 0;
    int k = p;
    while (k <= r) {
      if (leftArr[i] <= rightArr[j]) {
        arr[k++] = leftArr[i++];
      } else {
        arr[k++] = rightArr[j++];
      }
    }
  }
}
